package com.ting.test.algorithms.查找算法.归并查找;


/**
 * 给定一个数组arr，两个整数lower和upper，
 * <p>
 * 返回arr中有多少个子数组的累加和在[lower,upper]范围上
 */
public class 归并排序补充问题 {
    public static void main(String[] args) {
        int[] arr = new int[]{3, 4, 6, 7, 8, 9, 4, 2, 1, 7, 9,43,6,7,8,9,0,2,3,5,7,8,0,7};
        int L = 3;
        int R = 6;
        int[] sum = new int[arr.length];
        sum[0] = arr[0];
        for (int i = 1; i < sum.length; i++) {
            sum[i] = sum[i - 1] + arr[i];
        }

        int result1 = func(sum, 0, sum.length - 1, L, R);
        System.out.println(result1);
    }

    private static int func(int[] sum, int L, int R, int lower, int upper) {
        //base case
        if (L == R) {
            //sum[L]表示的是在arr数组中 0到L位置的前缀和
            return (sum[L] <= upper && sum[L] >= lower) ? 1 : 0;
        }
        int M = L + ((R - L) >> 1);
        int lc = func(sum, L, M, lower, upper);
        int rc = func(sum, M + 1, R, lower, upper);
        int mc = merge(sum, L, M, R, lower, upper);

        return lc + rc + mc;
    }
    /**
     *
     * @param sum
     * @param L
     * @param M
     * @param R
     * @param lower
     * @param upper
     * @return
     */
    private static int merge(int[] sum, int L, int M, int R, int lower, int upper) {
        int count = 0;
//        int WL,WR;
//        WL = L;
//        WR = L;
//        for (int i = M + 1; i <= R; i++) {
//            //当归并排序的merge在合并左右数组时 可以将合并过程做以下理解：
//            //sum[Rindex] 表示的是以Rindex为结尾的子数组的累加和
//            //sum[LIndex] 表示的是以Rindex为结尾 的 某一个前缀数组的累加和
//            //据此 我们求以Rindex结尾的子数组的累加和中有多少个 在[lower,upper]范围上
//            //也就是判在Rindex之前的前缀和中，有多少个在[sum[Rindex]-upper,sum[Rindex]-lower]范围上
//            //而Rindex之前的前缀和 就是merge左边的数组的所有元素
//            //那么也就只需要比较每个左边数组的元素是否落在了右边某个元素的[sum[Rindex]-upper,sum[Rindex]-lower]范围上
//            //需要注意  左右两个数组是有序递增的，相应的 对于右边的每一个值，其范围也是有序递增的
//            //也就是说 如果左边的元素i 不满足右边的元素j1的要求，那么他也一定不满足j1后面的所有元素的要求
//
//            int min = sum[i] - upper;
//            int max = sum[i] - lower;
//            // 注意 这种解法实际上时间复杂度是比较高的 for循环+while循环，还需要优化
//            while (WL <= M) {
//                if (sum[WL] >= min && sum[WL] <= max) {
//                    count++;
//                }
//                WL++;
//            }
//        }


        int windowL = L;
        int windowR = L;
        // [windowL, windowR)
        //需要注意  左右两个数组是有序递增的，相应的 对于右边的每一个值，其范围也是有序递增的
        //也就是说 如果左边的元素i 不满足右边的元素j1的要求，那么他也一定不满足j1后面的所有元素的要求
        for (int i = M + 1; i <= R; i++) {
            long min = sum[i] - upper;
            long max = sum[i] - lower;
            while (windowR <= M && sum[windowR] <= max) {
                windowR++;
            }
            while (windowL <= M && sum[windowL] < min) {
                windowL++;
            }
            count += windowR - windowL;
        }

        int LIndex = L;
        int Rindex = M + 1;
        int index = 0;
        int[] help = new int[R - L + 1];



        while (LIndex <= M && Rindex <= R) {

            help[index++] = sum[LIndex] <= sum[Rindex] ? sum[LIndex++] : sum[Rindex++];
        }

        while (LIndex <= M) {
            help[index++] = sum[LIndex++];
        }

        while (Rindex <= R) {
            help[index++] = sum[Rindex++];
        }
        for (int i = 0; i < help.length; i++) {
            sum[L + i] = help[i];
        }
        return count;
    }

    /**
     *
     * @param sum
     * @param L
     * @param M
     * @param R
     * @param lower
     * @param upper
     * @return
     */
    private static int merge2(int[] sum, int L, int M, int R, int lower, int upper) {
        int count = 0;
        int WL;
        for (int i = M + 1; i <= R; i++) {
            WL = L;
            //当归并排序的merge在合并左右数组时 可以将合并过程做以下理解：
            //sum[Rindex] 表示的是以Rindex为结尾的子数组的累加和
            //sum[LIndex] 表示的是以Rindex为结尾 的 某一个前缀数组的累加和
            //据此 我们求以Rindex结尾的子数组的累加和中有多少个 在[lower,upper]范围上
            //也就是判在Rindex之前的前缀和中，有多少个在[sum[Rindex]-upper,sum[Rindex]-lower]范围上
            //而Rindex之前的前缀和 就是merge左边的数组的所有元素
            //那么也就只需要比较每个左边数组的元素是否落在了右边某个元素的[sum[Rindex]-upper,sum[Rindex]-lower]范围上

            int min = sum[i] - upper;
            int max = sum[i] - lower;
            // 注意 这种解法实际上时间复杂度是比较高的 for循环+while循环，还需要优化
            while (WL <= M) {
                if (sum[WL] >= min && sum[WL] <= max) {
                    count++;
                }
                WL++;
            }
        }

        int LIndex = L;
        int Rindex = M + 1;
        int index = 0;
        int[] help = new int[R - L + 1];



        while (LIndex <= M && Rindex <= R) {

            help[index++] = sum[LIndex] <= sum[Rindex] ? sum[LIndex++] : sum[Rindex++];
        }

        while (LIndex <= M) {
            help[index++] = sum[LIndex++];
        }

        while (Rindex <= R) {
            help[index++] = sum[Rindex++];
        }
        for (int i = 0; i < help.length; i++) {
            sum[L + i] = help[i];
        }
        return count;
    }


}
